package leetcode;

import java.util.Arrays;
import java.util.List;

public class Lc150 {


    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rStart = slow.next; //slow的位置为中间位置，第二个区间的起始位置为slow.next
        slow.next = null; //把一个链表从中间切为两个链表

        ListNode left = sortList(head);
        ListNode right = sortList(rStart);
        ListNode dummyHead = new ListNode(-1);
        ListNode curNode = dummyHead;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                curNode.next = left;
                left = left.next;
            } else {
                curNode.next = right;
                right = right.next;
            }
            curNode = curNode.next;
        }
        curNode.next = left != null ? left : right;
        return dummyHead.next;
    }



//    public static void main(String[] args) {
//        Lc150 lc150 = new Lc150();
//        int[] arr = new int[]{3,4,2,1};
//        lc150.mergeSort(arr, 0 , 3);
//        Arrays.stream(arr).forEach(System.out::println);
//    }

}
